package leetcode;

import java.util.Scanner;

//二分查找答案
public class Chocolate {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int m=sc.nextInt();
        int n=sc.nextInt();
        int[][]arr=new int[m][2];
        for (int i = 0; i < arr.length; i++) {
            arr[i][0]=sc.nextInt();
            arr[i][1]=sc.nextInt();
        }
        int left=1,right=1000001,mid;
        int num=0;
        while (left<right){
             mid=(left+right)/2;
            if(SearchFor(mid,arr,n)){
                num=mid;
                left=mid+1;

            }else{
                right=mid;
            }
        }
//        while(left<right) {
//            mid = (left+right)/2;
//            if(SearchFor(mid,arr,n)) {
//                // 满足人吃 到右侧区间 增大边长 来试探右侧最小范围
//                left = mid+1;
//            }else {
//                //不满足k个人吃 到左侧区间
//                right = mid;
//            }
//        }
        System.out.println(num);

    }
    public static boolean SearchFor(int mid,int[][]arr,int k){//记录mid产生的巧克力
        int sum=0;
        for (int i = 0; i < arr.length; i++) {
            sum=sum+(arr[i][0]/mid)*(arr[i][1]/mid);//注意计算括号！！！！！！！！！！！！！！！！！！
        }
        if(sum>=k){
            return true;
        }else{
            return false;
        }
    }
}
//import java.util.Scanner;
//public class Chocolate {
//    //针对每块巧克力都是正方形 所以对一块大巧克力可以 以side为边长 遍历  (length/side)为在长边可以分出来的块数  （width/length）为在宽边可以分出来的块数
//    //两种边分出来的块数乘积 就是此巧克力可分的块数  算法解决：每块都至少是个1*1的情况 可以从1开始遍历  遍历到100000 但是算法的时间复杂度过大 可以考虑二分查找
//    //二分查找的时间复杂度log2n
//    static int n,k;     // n块巧克力  k个人分
//    static int num;  //巧克力分为k块
//    static int[][] chocolate = new int[100005][2];  //巧克力  二维数组上 保存宽和常
//    static Scanner sc = new Scanner(System.in);
//    public static void main(String[] args) {
//        n = sc.nextInt();
//        k = sc.nextInt();
//        for(int i = 0; i<n;i++) {
//
//            chocolate[i][0] = sc.nextInt();
//            chocolate[i][1] = sc.nextInt();
//        }
//        System.out.println(binary(1, 100001));
//    }
//
//    static int binary(int left,int right) {
//        int mid;
//        while(left<right) {
//            mid = (left+right)/2;
//            if(judge(mid)) {
//                // 满足人吃 到右侧区间 增大边长 来试探右侧最小范围
//                left = mid+1;
//            }else {
//                //不满足k个人吃 到左侧区间
//                right = mid;
//            }
//        }
//        //当满足 两者相等时 必然是一个不满足条件的 减去1可以找到那个最后满足条件的
//        return left-1;
//    }
//
//    static boolean judge(int side) {
//        int temp = 0;
//        for(int i = 0;i<n;i++) {
//            //遍历 所有的巧克力 确定针对这一边长 此巧克力可以取到的最多数的情况 然后加到一起
//            temp = temp + (chocolate[i][0]/side)*(chocolate[i][1]/side);
//        }
//        //当满足 k个人吃的时候 就是分配合理时候 递归可以往右侧区间  否则到左侧区间（减小边长来换取可以满足人吃）
//        if(temp>=k) {
//            return true;
//        }
//        return false;
//    }
//}